I. Field of the Invention
This invention relates generally to highly reliable, fault tolerant digital data processing systems, and more particularly to an N-modular redundancy microprocessor system in which the plural processors may be event-driven but remain in synchronization.
II. Discussion of the Prior Art
It is well known in the digital computing arts to employ a multiplicity of redundant processors to achieve fault tolerant operation, i.e., a microprocessor system capable of error-free operation in spite of one or more hardware faults. The most common prior art fault tolerant architecture is referred to as N-modular redundancy where N represents an odd number greater than one, and typically three or five. The N identical processors are programmed to execute identical programs in synchrony in response to a common set of input signals (data). Fault tolerance is achieved by continuously voting on the output signals produced by each processor in a majority decision logic voter. The result of the voting circuit is guaranteed to be correct, provided a majority of the processors compute a correct result. Synchronization may be established on instruction boundaries or, alternatively, for each processor clock cycle. In either case, voting is typically performed for each instruction, thus requiring that all processors execute identical programs in lock step.
It is also well known in the digital computing arts to employ interrupts to perform what is known as "event-driven computing". Interrupts allow the processor to function more efficiently in real-time applications, such as inertial navigation and flight control. In such systems, the processor is responsive to input signals which occur in real time, i.e., asynchronously with respect to the processor clock. Interrupts are the means by which program execution of an interrupt program sequence is temporarily suspended while an interrupt subroutine, often termed the service routine, processes the input data associated with the interrupt. The last step of any interrupt subroutine is the execution of a Return-From-Interrupt instruction such that execution of the instant program resumes exactly at the point where its suspension occurred.
Typical microprocessor systems are responsive to a multiplicity of interrupts and provide circuitry to prioritize and selectively mask interrupts. The Type 8259 Programmable Interrupt Controller manufactured by the Intel Corporation may be considered typical. Any real-time program must be written to assure that any combination of asynchronous events which generate interrupt requests will result in an orderly execution of the associated interrupt subroutines. To accomplish this, the interrupt controller must periodically strobe or sample the state of the multiple interrupt request lines with a signal derived from the processor clock. The set of interrupt request samples is processed by a priority encoder to determine which of simultaneous requests will be processed first. The interrupt controller then generates an interrupt signal to trigger execution of the associated service routine when the execution of the present instruction is complete.
Those skilled in the art can appreciate that it is not possible to assure the lock-step operation of plural redundant processors which is required for fault tolerant voting in accordance with the prior art when the processors are event-driven. When an interrupt request occurs simultaneous with the strobe signal, the results may be indeterminant. In spite of the best efforts to synchronize the processor clocks to one another and thereby synchronize interrupt request sampling, an event that one processor may resolve as "in time", i.e., occurring before the strobe signal, another processor may resolve as "too late", i.e., occurring after the strobe signal. The result is that the programs of the respective processors are interrupted at different points in the program and majority voting is no longer valid since synchronization is lost. In a like manner, two nearly simultaneous events may be serviced in one order in a first processor and in the reverse order in a second processor. This likewise invalidates the voting. Thus, the prior art use of N-modular redundancy generally precludes an event-driven processor architecture.
It is accordingly a principal object of the present invention to provide a means of processor synchronization which permits a processor redundant processor architecture to be both event driven and fault tolerant, yielding a system exhibiting high reliability and functional efficiency not heretofore found in the prior art.